package 算法.NiuKe.JZ;

import java.util.*;

/**
 * @author:谢君臣
 * @Date:2021/3/2218:03
 * @version:1.0
 * @function: 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class JZ26 {
    public static void main(String[] args) {
        Node node = new Node(4);
        node.left = new Node(2);
        node.left.left = new Node(1);
        node.left.right = new Node(3);
        node.right = new Node(5);
        Node node1 = treeToDoublyList(node);
        System.out.println();
    }
    public static Node treeToDoublyList(Node root) {
        if (root==null)
            return null;
        return DFS(root);
    }

    private static Node DFS(Node root) {
        Node head = null,pre = null;
        Stack<Node> stack = new Stack<>();
        while (root!=null||!stack.isEmpty()){
            while (root!=null){
                stack.add(root);
                root = root.left;
            }
            if (!stack.isEmpty()){
                root = stack.pop();
                if (head ==null) head = root;
                else{ pre.right = root;root.left = pre;}
                pre = root;
                root = root.right;
            }
        }
        return head;
    }
}
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
class Solution {
    public Node pre, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    public void dfs(Node cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(pre != null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}